package acwing.图;

import java.util.Arrays;
import java.util.Scanner;

/**
 * Dijkstra求最短路1
 *
 * @author yang
 * @date 2021/12/28
 */
public class Dijkstra求最短路1 {

    static int N = 510; // 最多存在的边
    // 题目中边只有500条 点有100000个是稠密图
    static int[] dist = new int[N]; // 每个点到原点的最短距离
    static int[][] g = new int[N][N]; // 模拟图
    static boolean[] dt = new boolean[N]; // 这个点上最短距离是否确定了
    static int n, m; // n 是边 m 是点

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();

        // 初始化
        for (int i = 1; i < n; i++) {
            Arrays.fill(g[i],0x3f3f3f3f);
        }
        m = sc.nextInt();
        while (m-- > 0) {
            int x, y, z;
            x = sc.nextInt();
            y = sc.nextInt();
            z = sc.nextInt();
            // 有重边，保留距离最短的
            g[x][y] = Math.min(g[x][y], z);
        }
        int t = dj();
        System.out.println(t);

    }

    private static int dj() {

        Arrays.fill(dist, 0x3f3f3f3f);
        dist[1] = 0; // 原点
        for (int i = 0; i < n; i++) { // n个点需要更新所有得迭代n次
            int t = -1;
            for (int j = 1; j <= n; j++) { // 找到距离最小的点
                if (!dt[j] && (t == -1 || dist[t] > dist[j])) {
                    t = j;
                }
            }
            dt[t] = true;
            for (int j = 1; j <= n; j++) {
                dist[j] = Math.min(dist[j], dist[t] + g[t][j]);
            }
        }
        if (dist[n] ==  0x3f3f3f3f) return -1;
        return dist[n];
    }
}
